package BinarySearch;

/*
寻找重复数
给定一个包含n + 1 个整数的数组nums ，其数字都在[1, n]范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3 :
输入：nums = [3,3,3,3,3]
输出：3

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/binary-search/xe6xnr/
 */

import java.util.Arrays;

public class _81寻找重复数 {
    public static void main(String[] args) {

    }

    //暴力
    //超时
    public int findDuplicate(int[] nums) {
        if(nums.length == 2) return nums[0];
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }
        return -1;
    }


    //官解： 二分查找       神
    //根据  小于mid数的次数来进行判断舍去左还是舍弃右
    //nums	1	2	3	4
    //cnt	1	3	4	5
    //将其转化为第一个错误版本问题
    class Solution {
        public int findDuplicate(int[] nums) {
            int n = nums.length;
            int l = 1, r = n - 1, ans = -1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                int cnt = 0;
                for (int i = 0; i < n; ++i) {
                    if (nums[i] <= mid) {
                        cnt++;
                    }
                }
                if (cnt <= mid) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                    ans = mid;
                }
            }
            return ans;
        }
    }

    //官解： 快慢双指针
    //成环链表
    class Solution2 {
        public int findDuplicate(int[] nums) {
            int slow = 0, fast = 0;
            do {
                slow = nums[slow];
                fast = nums[nums[fast]];
            } while (slow != fast);
            slow = 0;
            while (slow != fast) {
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }
    }

    //官解: 二进制
    class Solution3 {
        public int findDuplicate(int[] nums) {
            int n = nums.length, ans = 0;
            int bit_max = 31;
            while (((n - 1) >> bit_max) == 0) {
                bit_max -= 1;
            }
            for (int bit = 0; bit <= bit_max; ++bit) {
                int x = 0, y = 0;
                for (int i = 0; i < n; ++i) {
                    if ((nums[i] & (1 << bit)) != 0) {
                        x += 1;
                    }
                    if (i >= 1 && ((i & (1 << bit)) != 0)) {
                        y += 1;
                    }
                }
                if (x > y) {
                    ans |= 1 << bit;
                }
            }
            return ans;
        }
    }


}
